#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        vector<int> dp(len + 1);
        for (int i = 1; i <= len; i++)
            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
        int ret = INT_MIN;
        for (int i = 1; i <= len; i++)
            ret = max(ret, dp[i]);
        return ret;
    }
};

class Solutionx {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int len = nums.size();
        vector<int> dpmax(len + 1);
        vector<int> dpmin(len + 1);
        int sum = 0;
        int retmax = INT_MIN, retmin = INT_MAX;

        for (int i = 1; i <= len; i++) {
            sum += nums[i - 1];
            dpmax[i] = max(nums[i - 1], dpmax[i - 1] + nums[i - 1]);
            dpmin[i] = min(nums[i - 1], dpmin[i - 1] + nums[i - 1]);
            retmax = max(retmax, dpmax[i]);
            retmin = min(retmin, dpmin[i]);
        }
        if (sum == retmin)
            return retmax;
        return max(sum - retmin, retmax);
    }
};

class Solutionxx {
public:
    typedef long long intl;
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        vector<intl> f(len + 1), g(len + 1);
        intl ret = INT_MIN;
        f[0] = g[0] = 1;
        for (int i = 1; i <= len; i++) {
            intl x = nums[i - 1], y = nums[i - 1] * f[i - 1], z = nums[i - 1] * g[i - 1];
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(z, y));
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

int main() {
    Solutionx x;
    /*x.maxSubarraySumCircular({ -3, -2, -3 });*/
    return 0;
}